package com.kingwood.algorithm.test200;

import java.util.*;

/**
 * @Author 22025812
 * @Description: 二叉树计算
 * https://blog.csdn.net/qfc_128220/article/details/134607772
 * 主要就是根据二叉树的中序遍历和前序遍历还原二叉树
 * @Date: 2024/3/29 13:13
 * @Modified By：
 * @Version 1.0
 */
public class ErChaShu {
    static class TreeNode {
        int num;
        int childSum;
        TreeNode leftChild;
        TreeNode rightChild;

        TreeNode(int num) {
            this.num = num;
            this.childSum = 0;
            this.leftChild = null;
            this.rightChild = null;
        }
    }

    static int[] midOrder;
    static int[] preOrder;
    static HashMap<Integer, List<Integer>> midIndexMap = new HashMap<>();


    /**
     * 根据中序遍历序列、前序遍历序列还原树结构
     *
     * @param midL 中序遍历子序列的左边界
     * @param midR 中序遍历子序列的右边界
     * @param preL 前序遍历子序列的左边界
     * @param preR 前序遍历子序列的右边界
     * @return 树结构的根节点
     */
    public static TreeNode buildTree(int midL, int midR, int preL, int preR) {
        if (preL > preR) {
            return null;
        }

        // 先根据前序遍历序列得到根节点，前序序列的首元素就是根节点
        int rootNum = preOrder[preL];
        TreeNode root = new TreeNode(rootNum);

        for (int idx : midIndexMap.get(rootNum)) {
            // 如果对应根值位置越界，则不是正确的
            if (idx < midL || idx > midR) {
                continue;
            }
            // 如果中序的左子树，和前序的左子树不同，则对应根值位置不正确
            int leftLen = idx - midL;
            if (notEquals(midL, preL+1, leftLen)) {
                continue;
            }

            int rightLen = midR - idx;
            if (notEquals(idx + 1, preR- rightLen + 1, rightLen)) {
                continue;
            }

            root.leftChild = buildTree(midL, idx - 1, preL + 1, preL + leftLen);
            root.rightChild = buildTree(idx + 1, midR, preR - rightLen + 1, preR);

            root.childSum =  (root.leftChild == null ? 0 : (root.leftChild.num + root.leftChild.childSum))
                    + (root.rightChild == null ? 0 : (root.rightChild.num + root.rightChild.childSum));
        }

        return root;
    }

    public static boolean notEquals(int midL, int preL, int len) {
        int[] arr1 = Arrays.stream(Arrays.copyOfRange(midOrder, midL, midL + len)).sorted().toArray();
        int[] arr2 = Arrays.stream(Arrays.copyOfRange(preOrder, preL, preL + len)).sorted().toArray();

        for (int i = 0; i < len; i++) {
            if (arr1[i] != arr2[i]) {
                return true;
            }
        }

        return false;
    }

    public static void getMidOrder(TreeNode root, StringJoiner sj) {
        if (root == null) {
            return;
        }

       TreeNode leftChild = root.leftChild;
        if (leftChild != null) {
            getMidOrder(leftChild, sj);
        }

        sj.add(root.childSum + "");

        TreeNode rightChild = root.rightChild;
        if (rightChild != null) {
            getMidOrder(root.rightChild, sj);
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        midOrder = Arrays.stream(scanner.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        preOrder = Arrays.stream(scanner.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        int n = midOrder.length;
        for (int i = 0; i < n; i++) {
            int num = midOrder[i];
            midIndexMap.putIfAbsent(num, new ArrayList<>());
            midIndexMap.get(num).add(i);
        }

        TreeNode root = buildTree(0, n - 1, 0, n - 1);
        if (root == null) {
            System.out.println("");
        }

        StringJoiner sj = new StringJoiner(" ");
        getMidOrder(root, sj);
        System.out.println(sj.toString());
    }
}
